/*
 * @Description: 链表
 * @Autor: wangxin
 * @Date: 2020-06-11 09:57:49
 * @LastEditors: Please set LastEditors
 * @LastEditTime: 2020-06-12 20:13:09
 */
/**
 * 单向链表节点类
 */
class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}

/**
 * 单向链表
 */
class LinkedList {
  constructor() {
    this.count = 0
    this.head = null
  }

  /**
   * 向链表尾部添加新元素
   */
  push(element) {
    const node = new Node(element)
    let current
    if (this.head == null) {
      this.head = node
    } else {
      current = this.head
      // 获得最后一项
      while (current.next != null) {
        current = current.next
      }
      // 将next赋为新元素，建立链接
      current.next = node
    }

    this.count++
  }
  /**
   * 循环迭代链表直到目标位置
   */
  getElementAt(index) {
    if (index < 0 || index >= this.count) {
      return undefined
    }
    let current = this.head
    for (let i = 0; i < index; i++) {
      current = current.next
    }
    return current
  }
  /**
   * 从链表中特定位置移除一个元素
   */
  removeAt(index) {
    // 检查越界值
    if (index < 0 || index >= this.count) {
      return undefined
    }
    let current = this.head
    // 移除第一项
    if (index === 0) {
      this.head = current.next
    } else {
      const previous = this.getElementAt(index - 1)
      // 需要被移除的项
      current = previous.next
      // 跳过current，从而移除它
      previous.next = current.next
    }
    this.count--
    return current.element
  }
  /**
   * 在任意位置插入元素
   */
  insert(element, index) {
    // 检查越界值
    if (index < 0 || index > this.count) {
      return false
    }
    const node = new Node(element)

    // 在第一个位置插入元素
    if (index === 0) {
      const current = this.head
      node.next = current
      this.head = node
    } else {
      // 插入新元素的前一个元素
      const previous = this.getElementAt(index - 1)
      // 插入新元素的后一个元素
      const current = previous.next
      node.next = current
      previous.next = node
    }
    this.count++
    return true
  }
  /**
   * 返回一个元素的位置，没有找到返回-1
   */
  indexOf(element) {
    let current = this.head

    for (let i = 0; i < this.count; i++) {
      if (current.element == element) {
        return i
      }
      current = current.next
    }
    // 没有找到
    return -1
  }
  /**
   * 把链表转换成一个字符串
   */
  toString() {
    if (this.head == null) {
      return ''
    }
    let objString = `${this.head.element}`
    let current = this.head.next
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${current.element}`
      current = current.next
    }
    return objString
  }
  /**
   * 从链表中移除元素
   */
  remove(element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }
  /**
   * 判断链表是否有元素
   */
  isEmpty() {
    return this.count === 0
  }
  /**
   * 返回链表的长度
   */
  size() {
    return this.count
  }
  /**
   * 返回链表的头部元素
   */
  getHead() {
    return this.head.element
  }
}

// 代码测试
// var list = new LinkedList()
// list.push(1)
// list.push(2)
// list.push(3)
// console.log(list.toString())
